题目：删除二叉搜索树中满足某个条件的节点

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
	public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) {
        return null;
      }
      
      if (root.val < key) {
        root.right = deleteNode(root.right, key);
        return root;
      }
      
      if (root.val > key) {
        root.left = deleteNode(root.left, key);
        return root;
      }
      
      if (root.left == null && root.right == null) {
        root = null;
        return root;
      }
      
      if (root.left != null &&root.right == null) {
        root = root.left;
        return root;
      }
      
      if (root.left == null && root.right != null) {
        root = root.right;
        return right;
      }
      
      // 重新调整二叉树，首先在左子树中找出最大值，将最大值赋值给根结点，然后删除左子树中值最大的节点，新的子树赋值给根结点的左子树
      if (root.left != null && root.right != null) {
        int val = findMaxInLeftTree(root.left);
        root.val = val;
        root.left = deleteNode(root.left, val);
        return root;
      }
      
      return root;
	}  
  
  	int findMaxInLeftTree(TreeNode node) {
      if (node == null) { // 空节点，直接返回
        return 0;
      }
      
      if (node.right == null) { // 右子树的节点的值比根结点的值大，若右子树为空，则直接返回根结点的值
        return node.val;
      }
      
      if (node.right == null && node.left == null) { // 左子树和右子树均为空，则直接返回根结点的值
        return node.val;
      }
      
      return findMaxInLeftTree(node.right); // 左子树和右子树都不为空，最大值必然在右子树中，则递归找出右子树中的最大值
  	}
}